ProgrammingAlgorithm

백준 2250 트리의 높이와 너비

백준 2250 트리의 높이와 너비

백준 2250 트리의 높이와 너비는 트리의 노드에 번호를 붙이고, 같은 레벨에 있는 최대 노드 번호 - 최소노드 번호 +1의 값이 가장 큰 즉 너비가 가장 넓은 레벨과 너비의 값을 출력하는 문제이다.

이 과정에서 트리의 번호를 어떻게 매기는가는 문제의 그림을 보면 쉽게 알 수 있다. 위에서 2번 번호를 가진 노드를 보자. 2번을 기준으로 번호를 매길 때 왼쪽 끝까지 들어가서 번호를 매기는 것을 볼 수 있고 오른쪽 자식들의 경우 왼쪽을 우선적으로 매기고 오른쪽을 나중에 매기는 것을 알 수 있다. -> 따라서 이 경우 중위 순회를 하며 index를 매기고 있다.

즉 이 문제는 들어온 입력값으로 트리를 구성한 뒤 중위 순회로 번호를 매기고 같은 레벨에서의 최소, 최대 번호 값을 찾아 비교하는 문제이다.

입력값이 10000까지 들어오고 노드의 번호는 불규칙 할 수 있기 때문에 먼저 n개의 노드를 생성하고 배열에 저장했다. 생성한 노드는 입력값인 root, left, right의 해당 노드를 배열에서 찾아 연결하며 트리를 구성했다. 그리고 여기서 가장 중요한 점은 root가 항상 1번 노드가 아니라는 점이다. -> 이 예외를 찾지 못해 고생했다.

1번 노드가 아니기 때문에 배열을 하나 더 만들어서 자신이 자식으로 들어가면 flag를 채운뒤 나중에 flag가 없는 번호의 노드가 root가 될 것이기 때문에 이 방법으로 루트를 찾았다.

그 다음 레벨 별로 트리의 너비를 계산하기 위해 레벨 순회를 하며 최소 번호값과 최대 번호값을 찾으며 마지막에는 이전의 값과 비교하여 최대인지 확인한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
#include<string.h>
#include<set>
#include<cmath>
#define INF 987654321

using namespace std;

int n;

int numb = 1;

int mn = INF;
int mx = -INF;
typedef struct Node
{
	int idx;
	Node* left;
	Node* right;
}Node;

Node* arr[10001];

int isChild[10001];

void dfs(Node** current)
{
	if ((*current)->left != NULL)
		dfs(&(*current)->left);

	(*current)->idx = numb++;

	if ((*current)->right != NULL)
		dfs(&(*current)->right);
}

void levelOrder(Node** cur, int d,int level)
{
	if (d == level)
	{
		mn = min(mn, (*cur)->idx);
		mx = max(mx, (*cur)->idx);
	}
	if ((*cur)->left != NULL)
		levelOrder(&(*cur)->left, d + 1, level);
	if ((*cur)->right != NULL)
		levelOrder(&(*cur)->right, d + 1, level);
}

int main()
{
	//freopen("input.txt", "r", stdin);

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		arr[i] = new Node({ -1, NULL, NULL });
	}

	for (int i = 1; i <= n; i++)
	{
		int root, left, right;
		cin >> root >> left >> right;
		if (left != -1)
		{
			arr[root]->left = arr[left];
			isChild[left] = 1;
		}
		if (right != -1)
		{
			arr[root]->right = arr[right];
			isChild[right] = 1;
		}
	}

	int root = -1;
	for (int i = 1; i <= n; i++)
	{
		if (isChild[i] == 0)
		{
			root = i;
			break;
		}
	}

	dfs(&arr[root]);

	int h = (int)ceil(log2(n));
	int ret = 0;
	int retidx = -1;
	for (int i = 1; i <= h + 1; i++)
	{
		mn = INF;
		mx = -INF;
		levelOrder(&arr[root], 1, i);
		if (ret < mx - mn + 1)
		{
			ret = mx - mn + 1;
			retidx = i;
		}
	}

	cout << retidx << ' ' << ret << endl;

	return 0;

}
공유하기